Anti-replay protection is used in data networks to prevent “attacks” that may result from so-called replay of packets to a network device. For example, time-based anti-replay protection involves examining a timestamp of a packet and discarding the packet when the timestamp of the packet is older than a predetermined period of time. Time-based anti-replay protection techniques are not adequate for certain applications that are sensitive to replayed packets such as multicast routing updates, because the packets can still be replayed within a finite time window. Voice and video applications are particularly sensitive to the sequencing of the packets and need strong replay protection.